#include <vector>
#include <algorithm>
#include <climits>
#include <iostream>
using namespace std;

class Code02_MinimumCostForTickets
{
public:
    // 无论提交什么方法都带着这个数组      0  1  2
    static const vector<int> durations;

    // 暴力尝试
    static int mincostTickets1(vector<int> &days, vector<int> &costs)
    {
        return f1(days, costs, 0);
    }

    // days[i..... 最少花费是多少
    static int f1(vector<int> &days, vector<int> &costs, int i)
    {
        if (i == days.size())
        {
            // 后续已经无旅行了
            return 0;
        }
        // i下标 : 第days[i]天，有一场旅行
        // i.... 最少花费是多少
        int ans = INT_MAX;
        for (int k = 0, j = i; k < 3; k++)
        {
            // k是方案编号 : 0 1 2
            while (j < days.size() && days[i] + durations[k] > days[j])
            {
                // 因为方案2持续的天数最多，30天
                // 所以while循环最多执行30次
                // 枚举行为可以认为是O(1)
                j++;
            }
            ans = min(ans, costs[k] + f1(days, costs, j));
        }
        return ans;
    }

    // 暴力尝试改记忆化搜索
    // 从顶到底的动态规划
    static int mincostTickets2(vector<int> &days, vector<int> &costs)
    {
        vector<int> dp(days.size(), INT_MAX);
        return f2(days, costs, 0, dp);
    }

    static int f2(vector<int> &days, vector<int> &costs, int i, vector<int> &dp)
    {
        if (i == days.size())
        {
            return 0;
        }
        if (dp[i] != INT_MAX)
        {
            return dp[i];
        }
        int ans = INT_MAX;
        for (int k = 0, j = i; k < 3; k++)
        {
            while (j < days.size() && days[i] + durations[k] > days[j])
            {
                j++;
            }
            ans = min(ans, costs[k] + f2(days, costs, j, dp));
        }
        dp[i] = ans;
        return ans;
    }

    // 严格位置依赖的动态规划
    // 从底到顶的动态规划
    static const int MAXN = 366;

    static int dp[MAXN];

    static int mincostTickets3(vector<int> &days, vector<int> &costs)
    {
        int n = days.size();
        fill(dp, dp + n + 1, INT_MAX);
        dp[n] = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            for (int k = 0, j = i; k < 3; k++)
            {
                while (j < days.size() && days[i] + durations[k] > days[j])
                {
                    j++;
                }
                dp[i] = min(dp[i], costs[k] + dp[j]);
            }
        }
        return dp[0];
    }
};

// 初始化静态成员变量
const vector<int> Code02_MinimumCostForTickets::durations = {1, 7, 30};
int Code02_MinimumCostForTickets::dp[MAXN];

int main()
{
    vector<int> days = {1, 4, 6, 7, 8, 20};
    vector<int> costs = {2, 7, 15};

    int result1 = Code02_MinimumCostForTickets::mincostTickets1(days, costs);
    int result2 = Code02_MinimumCostForTickets::mincostTickets2(days, costs);
    int result3 = Code02_MinimumCostForTickets::mincostTickets3(days, costs);

    // 输出结果
    cout << "Result 1: " << result1 << endl;
    cout << "Result 2: " << result2 << endl;
    cout << "Result 3: " << result3 << endl;

    return 0;
}
